#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* n1 = NULL, * n2 = head, * n3 = head->next;
//    while (n2)
//    {
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//        if (n3 != NULL)
//            n3 = n3->next;
//
//    }
//    return n1;
//
//}
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
//{
//	struct ListNode* lst1 = list1;
//	struct ListNode* lst2 = list2;
//	struct ListNode* last = (struct ListNode*)malloc(sizeof(struct ListNode));
//	last->next = NULL;
//	struct ListNode* slip = last;
//	while (lst1 && lst2)
//	{
//		if (lst1->val <= lst2->val)
//		{
//			slip->next = lst1;
//			slip = slip->next;
//			lst1 = lst1->next;
//
//		}
//		else
//		{
//			slip->next = lst2;
//			slip = slip->next;
//			lst2 = lst2->next;
//		}
//		
//	}
//	if (lst1 == NULL)
//	{
//		slip->next = lst2;
//	}
//	if (lst2 == NULL)
//	{
//		slip->next = lst1;
//	}
//	return last->next;
//}


//ListNode* partition(ListNode* pHead, int x)
//{
//
//	ListNode* last1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	ListNode* last2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	ListNode* slip1 = last1;
//	ListNode* slip2 = last2;
//	ListNode* cur = pHead;
//	while (cur)
//	{
//		if (cur->val < x)
//		{
//			slip1->next = cur;
//			slip1 = slip1->next;
//
//		}
//		else
//		{
//			slip2->next = cur;
//			slip2 = slip2->next;
//
//		}
//		cur = cur->next;
//	}
//	slip1->next = last2->next;
//	slip2->next = NULL;
//
//	pHead = last1->next;
//	free(last1);
//	free(last2);
//	return pHead;
//}

bool chkPalindrome(ListNode* A) 
{
	// write code here
	if (A == NULL)
		return NULL;
	ListNode* n1 = NULL, * n2 = A, * n3 = A->next;
	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if(n3!=NULL)
			n3 = n3->next;

	}
	while (A)
	{
		if (A->val != n1->val)
			return false;
		A = A->next;
		n1 = n1->next;
	}
	return true;

}

void Listprin(struct ListNode* head)
{
	struct ListNode* tail = head;
	while (tail)
	{
		printf("%d->", tail->val);
		tail = tail->next;
	}
	printf("NULL\n");
}
int main()
{
	 ListNode* n1 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n2 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n3 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n4 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n5 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n6 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n7 = ( ListNode*)malloc(sizeof(struct ListNode));
	 ListNode* n8 = ( ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;
	n2->val = 2;
	n3->val = 2;
	n4->val = 1;
	n5->val = 1;
	n6->val = 2;
	n7->val = 2;
	n8->val = 1;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = n8;
	n8->next = NULL;

	/*struct ListNode* s1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* s2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* s3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* s4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	s1->val = 5;
	s2->val = 6;
	s3->val = 8;
	s4->val = 10;

	s1->next = s2;
	s2->next = s3;
	s3->next = s4;
	s4->next = NULL;*/
	Listprin(n1);
	/*struct ListNode* head = mergeTwoLists(n1,s1);*/
	bool head = chkPalindrome(n1);
	//struct ListNode* head = reverseList(n1);
	printf("%d\n", head);
	//Listprin(head);
	return 0;
}